<?php
/**
 * <https://y.st./>
 * Copyright © 2019 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Deadlocks',
	'<{subtitle}>' => 'Written in <span title="Databases 2">CS 3306</span> by <a href="https://y.st./">Alexand(er|ra) Yst</a>, finalised and <a href="https://y.st./en/coursework/CS3306/Entity-relationship_diagram.xhtml">archived</a> on 2019-04-24',
	'<{copyright year}>' => '2019',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<div class="APA_title_page">
	<p>
		Deadlocks<br/>
		Alexand(er|ra) Yst<br/>
		<span title="Databases 2">CS 3306</span>
	</p>
</div>
<p>
	It&apos;s possible to create a database system that doesn&apos;t suffer from deadlocks <a href="https://my.uopeople.edu/pluginfile.php/476000/mod_book/chapter/187010/Database%20System%20Concepts%204th%20Edition%20By%20Silberschatz-Korth-Sudarshan.pdf">(Silberschatz-Korth-Sudarshan, 2001)</a>.
	However, not all database systems are created with such preventative measures.
	An alternative to preventing problems before they start is to fix problems after they occur, an approach taken by other database systems.
	Personally, I think a gram of prevention is worth a kilogram of cure, but maybe that&apos;s just me.
	In any case, when deadlocks are allowed to occur, one way to correct the situation is to roll back one or more of the offending transactions so as to break the deadlock.
	There are three steps in breaking a deadlock in such a manner.
</p>
<h2>Selection of a victim or victims</h2>
<p>
	First, the database software must decide which transactions will be rolled back <a href="https://my.uopeople.edu/pluginfile.php/476000/mod_book/chapter/187010/Database%20System%20Concepts%204th%20Edition%20By%20Silberschatz-Korth-Sudarshan.pdf">(Silberschatz-Korth-Sudarshan, 2001)</a>.
	Which transactions will be nullified?
	Generally, it&apos;s best to try to reduce costs when determining what to roll back, but this isn&apos;t an easy task.
	There are several competing things one can optimise for.
	Do you want to roll back the fewest commits you have to to break the deadlock?
	Do you want to undo the least amount of changes to the database?
	Do you want to cause the least amount of time to have been wasted by the transactions thus far?
	Do you want to leave transactions that are closer to committing alone so they&apos;ll reach a completed state?
	What you optimise for is likely dependant on your use case and your situation, and the lack of a hard-and-fast rule makes it more difficult.
</p>
<h2>Rollback</h2>
<p>
	Once your selections have been made, it&apos;s time to perform the actual rollback.
	Rollback does necessarily mean a total and complete rollback, though this is the simplest option.
	Another option is to roll back the transaction partly, then allow it to pick up at that point and try again.
	This option is more complex though, and requires more preparation.
	With a total rollback, you can simply start the transaction again from the beginning.
	With a partial rollback, state information for each running transaction is needed, so you can go back to a previous point in the transaction.
	Such state information needs to be kept as the transaction is initially attempted, and can&apos;t simply be generated after the fact when something goes wrong.
	Mainly, it&apos;s the series of lock requests and releases that need to be recorded.
	Using this log, the database can roll back specifically to the point just before the lock that needs to be release was requested, effectively making it so the lock hasn&apos;t yet been granted in the first place.
	To roll back, every change in the database made after that point within that transaction has to be undone <a href="https://my.uopeople.edu/pluginfile.php/476000/mod_book/chapter/187010/Database%20System%20Concepts%204th%20Edition%20By%20Silberschatz-Korth-Sudarshan.pdf">(Silberschatz-Korth-Sudarshan, 2001)</a>.
</p>
<h2>Starvation prevention</h2>
<p>
	The final step to breaking deadlocks via rollback is to prevent transaction starvation.
	Basically, if a transaction was chosen as the victim or one of the victims, there&apos;s a reason for it, and that reason likely persists after the rollback and after the deadlock id broken.
	If deadlocks occur frequently, that same transaction may get rolled back countless times and never actually get a chance to complete.
	TO prevent that, a counter needs to be used to determine how many times a given transaction has been chosen as the victim to be rolled back.
	One way to use this counter would be to involve it in the cost factor when determining which transactions to select as victims <a href="https://my.uopeople.edu/pluginfile.php/476000/mod_book/chapter/187010/Database%20System%20Concepts%204th%20Edition%20By%20Silberschatz-Korth-Sudarshan.pdf">(Silberschatz-Korth-Sudarshan, 2001)</a>.
</p>
<h2>Conclusion</h2>
<p>
	As I said before, it seems like a better idea to prevent deadlocks than work to break them when they occur.
	I think the problem of transaction starvation just goes to show how frequently they can happen when preventative measures aren&apos;t taken.
	However, a great deal of work has been put into making database software that allows deadlocks to occur still function as intended even despite the deadlocks it encounters.
	Therefore, there&apos;s no need to worry about using database software that allows deadlocks.
	The programmers usually know what they&apos;re doing, had have accounted for this frequent occurrence.
	Software making use of database software can reliably depend on transactions remaining atomic, concurrent, isolated, and durable.
</p>
<div class="APA_references">
	<h2>References:</h2>
	<p>
		Silberschatz-Korth-Sudarshan. (2001). <a href="https://my.uopeople.edu/pluginfile.php/476000/mod_book/chapter/187010/Database%20System%20Concepts%204th%20Edition%20By%20Silberschatz-Korth-Sudarshan.pdf">Database System Concepts, Fourth Edition</a>. Retrieved from <code>https://my.uopeople.edu/pluginfile.php/476000/mod_book/chapter/187010/Database%20System%20Concepts%204th%20Edition%20By%20Silberschatz-Korth-Sudarshan.pdf</code>
	</p>
</div>
END
);
